package com.zx._12_算法.数据结构.bitmap;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: SimpleBitMap
 * @Description: 布隆过滤器
 *         前面所讲的BitMap的确很厉害，可是，却有着很强的局限性，BitMap只能用来处理整数，无法用于处理字符串，假设让你写一个强大的爬虫，每天爬取数以亿计的网页，
 *         那么你就需要一种数据结构，能够存储你已经爬取过的url，这样，才不至于重复爬取。
 *
 *         你可能会想到使用hash函数对url进行处理，转成整数，这样，似乎又可以使用BitMap了，但这样还是会有问题。假设BitMap能够映射的最大值是M，一个url的hash值需要对M求模，
 *         这样，就会产生冲突，而且随着存储数据的增多，冲突率会越来越大。
 *
 *         布隆过滤器的思想非常简单，其基本思路和BitMap是一样的，可以把布隆过滤器看做是BitMap的扩展。
 *         为了解决冲突率，布隆过滤器要求使用k个hash函数，新增一个key时，把key散列成k个整数，然后在数组中将这个k个整数所对应的二进制位设置为1，判断某个key是否存在时，
 *         还是使用k个hash函数对key进行散列，得到k个整数，如果这k个整数所对应的二进制位都是1，就说明这个key存在，否则，这个key不存在。
 *
 *         对于一个布隆过滤器，有两个参数需要设置，一个是预估的最多存放的数据的数量，一个是可以接受的冲突率。
 *         假设预估最多存放n个数据，可已接受的冲突率是p，那么就可以计算出来布隆过滤器所需要的bit位数量m,也可以计算所需要的hash函数的个数k。
 * @author: zhangxue
 * @date: 2019年7月31日下午10:43:24
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class BloomFilter {

    // 位图映射变量
    int[] bitMap;

    // 最多可放的数量
    int maxCount;

    // 错误率, < 1
    double errorRate;

    // 位图变量的长度，bitMap的长度
    int bitSize;

    // 哈希数量,表示计算几次hash
    int hashCount;

    // 压缩因子
    int divisor = 32;

    public BloomFilter(int maxCount, double errorRate) {
        this.maxCount = maxCount;
        this.errorRate = errorRate;
        this.bitSize = (int) Math.ceil(maxCount * (-Math.log(errorRate) / (Math.log(2D) * Math.log(2D))));
        this.hashCount = (int) Math.ceil(Math.log(2) * (bitSize / maxCount));
        this.bitMap = new int[bitSize * hashCount];
    }

    public static void main(String[] args) {
        BloomFilter bloomFilter = new BloomFilter(1000000, 0.01);
        System.out.println(bloomFilter.toString());
        bloomFilter.add("https://blog.csdn.net/houzuoxin/article/details/20907911");
        bloomFilter.add("https://www.jianshu.com/p/888c5eaebabd");

        System.out.println(bloomFilter.isExist("https://blog.csdn.net/houzuoxin/article/details/20907911"));// true
        System.out.println(bloomFilter.isExist("https://www.jianshu.com/p/888c5eaebabd"));// true
        System.out.println(bloomFilter.isExist("https://www.jianshu.com/p/888c5eaebabd435"));// false
    }

    @Override
    public String toString() {
        return "BloomFilter [bitMap.length=" + bitMap.length + ", maxCount="
                + maxCount + ", errorRate=" + errorRate + ", bitSize=" + bitSize
                + ", hashCount=" + hashCount + ", divisor=" + divisor + "]";
    }

    public boolean add(String member) {
        if (this.isExist(member)) {
            return false;  //表示已经存在
        }

        for (int i = 0; i < hashCount; i++) {
            int hash = this.murmurhash3_32_gc(member, i);
            int arrIndex = hash / divisor;
            int bitIndex = hash % divisor;
            bitMap[arrIndex] = bitMap[arrIndex] | 1 << bitIndex;
        }
        return true;
    }

    public boolean isExist(String member) {
        for (int i = 0; i < hashCount; i++) {
            int hash = this.murmurhash3_32_gc(member, i);
            int arrIndex = hash / divisor;
            int bitIndex = hash % divisor;

            int bitValue = bitMap[arrIndex];

            int res = bitValue & (1 << bitIndex);
            if (res == 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * @Title: 哈希函数就是将某一不定长的对象映射为另一个定长的对象，如果你对这个概念感到困惑，你就换一个理解方法，你给hash函数传入一个字符串，
     *         它返回一个整数。为了实现一个布隆过滤器，我们需要一个好的hash函数，计算快，冲突又少，
     *         很幸运，有很多开源的hash算法，我在github上找到了一个murmurhash的实现
     *
     *         murmurhash3_32_gc函数接受两个值，
     *         member是需要散列的对象，
     *         seed是种子，同一个member，不同的种子会返回不同的结果，这正是我们想要的，布隆过滤器需要k个hash值，对于一个member，传入k个种子就可以得到k个散列结果了。
     */
    private int murmurhash3_32_gc(String member, int seed) {
        int remainder, bytes, h1, h1b, c1, c1b, c2, c2b, k1, i;
        remainder = member.length() & 3;
        bytes = member.length() - remainder;
        h1 = seed;
        c1 = 0xcc9e2d51;
        c2 = 0x1b873593;
        i = 0;
        while (i < bytes) {
            k1 =
                    ((member.charAt(i) & 0xff)) |
                            ((member.charAt(++i) & 0xff) << 8) |
                            ((member.charAt(++i) & 0xff) << 16) |
                            ((member.charAt(++i) & 0xff) << 24);
            ++i;

            k1 = ((((k1 & 0xffff) * c1) + ((((k1 >>> 16) * c1) & 0xffff) << 16))) & 0xffffffff;
            k1 = (k1 << 15) | (k1 >>> 17);
            k1 = ((((k1 & 0xffff) * c2) + ((((k1 >>> 16) * c2) & 0xffff) << 16))) & 0xffffffff;

            h1 ^= k1;
            h1 = (h1 << 13) | (h1 >>> 19);
            h1b = ((((h1 & 0xffff) * 5) + ((((h1 >>> 16) * 5) & 0xffff) << 16))) & 0xffffffff;
            h1 = (((h1b & 0xffff) + 0x6b64) + ((((h1b >>> 16) + 0xe654) & 0xffff) << 16));
        }

        k1 = 0;

        switch (remainder) {
            case 3:
                k1 ^= (member.charAt(i + 2) & 0xff) << 16;
            case 2:
                k1 ^= (member.charAt(i + 1) & 0xff) << 8;
            case 1:
                k1 ^= (member.charAt(i) & 0xff);

                k1 = (((k1 & 0xffff) * c1) + ((((k1 >>> 16) * c1) & 0xffff) << 16)) & 0xffffffff;
                k1 = (k1 << 15) | (k1 >>> 17);
                k1 = (((k1 & 0xffff) * c2) + ((((k1 >>> 16) * c2) & 0xffff) << 16)) & 0xffffffff;
                h1 ^= k1;
        }

        h1 ^= member.length();

        h1 ^= h1 >>> 16;
        h1 = (((h1 & 0xffff) * 0x85ebca6b) + ((((h1 >>> 16) * 0x85ebca6b) & 0xffff) << 16)) & 0xffffffff;
        h1 ^= h1 >>> 13;
        h1 = ((((h1 & 0xffff) * 0xc2b2ae35) + ((((h1 >>> 16) * 0xc2b2ae35) & 0xffff) << 16))) & 0xffffffff;
        h1 ^= h1 >>> 16;

        return (int) Math.abs(Math.floor(h1 >>> 0));
    }

}
